Part 1

Playing Jenga with the elves

First, create the bricks

input <- read_lines("Day22Sample.txt")

bricks<-as.data.frame(matrix(ncol=6,nrow=0))
for(i in 1:length(input)){
  bricks<-rbind(bricks,as.numeric(unlist(str_split(str_replace(input[i],"~",","),","))))}
colnames(bricks)<-c("x1","y1","z1","x2","y2","z2")

### add 1 because working with R instead of a language that starts at 0.
bricks<-bricks+1

Now, sort the bricks by the lowest Z, then add a number to show which block is first (& so on)

bricks <- bricks %>% rowwise %>% mutate(lowz=min(z1,z2)) %>% arrange(lowz) %>%
  rowid_to_column(var="bricknum") %>% mutate(bricknum=paste0("brick",bricknum))
bricks[1:5,]

With the bricks sorted, creating an artifical “tower” for them to settle into. It will be a three dimensional array and the lowest layer will be “floor”

Create Container and Graph (mostly for part 2)

tower <- array(character(),
               c(max(bricks$x1,bricks$x2),
                 max(bricks$y1,bricks$y2),
                 max(bricks$z1,bricks$z2)))
tower[,,1]<-"floor"

Function to settle the blocks into the tower and create a support graph:

settle<-function(blist,twr){
  ### create a support graph
  supportgraph<-matrix(ncol=2,nrow=0)
  ### create a new dataframe
  tinyb<-as.data.frame(matrix(ncol=9,nrow=0))
  ### for each row of the bricklist
  for(i in 1:nrow(blist)){
    keepgoing<-TRUE
    currbr<-blist[i,]
    howmanylevels<-dim(twr)[3]
      for(x in currbr$x1:currbr$x2){
        for(y in currbr$y1:currbr$y2){
          for(z in currbr$z1:currbr$z2){
            highestfilled<-max(which(!is.na(twr[x,y,1:(currbr$lowz-1)])))
            howmanylevels<-min(howmanylevels,z-highestfilled-1)}}}
    currbr$z1<-currbr$z1-howmanylevels
    currbr$z2<-currbr$z2-howmanylevels
    currbr$lowz<-currbr$lowz-howmanylevels
    ### once it has dropped as far as possible, add the brickname to the tower
    for(x in currbr$x1:currbr$x2){
      for(y in currbr$y1:currbr$y2){
        for(z in currbr$z1:currbr$z2){
          twr[x,y,z]<-currbr$bricknum
          if(!is.na(twr[x,y,(z-1)])){supportgraph<-rbind(supportgraph,c(twr[x,y,(z-1)],currbr$bricknum))}
          }}}
    ### add the new brick position to the new bricklist
    tinyb<-rbind(tinyb,currbr)}
  ### clean up the repeat edges in the support graph & create the support graph
  supportgraph <- unique(supportgraph)
  supportgraph <-simplify(graph_from_edgelist(as.matrix(supportgraph)))
  colnames(tinyb)<-colnames(blist)
  ### return the updated tower, the new bricklist and the list of all connections between bricks
  list(twr,tinyb,supportgraph)}

Run on the data

settling<-settle(bricks,tower)
settledbricks<-settling[[2]]
settledtower<-settling[[1]]
settledgraph<-settling[[3]]

Here’s a visual of the real data both before and after settling:

The support graph shows a connection between every brick and the bricks it is resting on. A brick is stable if there is a connection between it and the floor.

One way to test is to remove a brick and then see if all of the other bricks still have a connection to the floor. If so, then it can be safely disintegrated. If not, then that brick is not safe

part1<-0
for(i in 1:nrow(settledbricks)){
  checkgraph<-delete.vertices(settledgraph,settledbricks[i,]$bricknum)
  q<-distances(checkgraph,v="floor",to=V(checkgraph),mode=c("out"))[1,]
  if(all(q!=Inf)){part1<-part1+1}}

part1
[1] 5

Part 2 -

Find the chain reactions:

part2<-0

### same as before, but instead of counting the safe bricks, count the number that would fall

for(i in 1:nrow(settledbricks)){
  checkgraph<-delete.vertices(settledgraph,settledbricks[i,]$bricknum)
  q<-distances(checkgraph,v=1,to=V(checkgraph),mode=c("out"))[1,]
  part2<-part2 + length(which(q==Inf))}

part2
[1] 7
day22answers <-function(input){
### set up bricks
  bricks<-as.data.frame(matrix(ncol=6,nrow=0))
for(i in 1:length(input)){
  bricks<-rbind(bricks,as.numeric(unlist(str_split(str_replace(input[i],"~",","),","))))}
colnames(bricks)<-c("x1","y1","z1","x2","y2","z2")

### add 1 because working with R instead of a language that starts at 0.
bricks<-bricks+1
bricks <- bricks %>% rowwise %>% mutate(lowz=min(z1,z2)) %>% arrange(lowz) %>%
  rowid_to_column(var="bricknum") %>% mutate(bricknum=paste0("brick",bricknum))
### set up tower
tower <- array(character(),
               c(max(bricks$x1,bricks$x2),
                 max(bricks$y1,bricks$y2),
                 max(bricks$z1,bricks$z2)))
tower[,,1]<-"floor"

### run settling
settling<-settle(bricks,tower)
settledbricks<-settling[[2]]
settledtower<-settling[[1]]
settledgraph<-settling[[3]]  

### run parts 1 & 2

part1<-0
part2<-0
for(i in 1:nrow(settledbricks)){
  checkgraph<-delete.vertices(settledgraph,settledbricks[i,]$bricknum)
  q<-distances(checkgraph,v="floor",to=V(checkgraph),mode=c("out"))[1,]
  if(all(q!=Inf)){part1<-part1+1}
  part2<-part2 + length(which(q==Inf))}
  c(part1,part2)}
day22 <- day22answers(input)
day22
[1] 5 7
LS0tDQp0aXRsZTogIkRheSAyMiBOb3RlYm9vayINCm91dHB1dDogaHRtbF9ub3RlYm9vaw0KLS0tDQoNCmBgYHtyIHNldHVwLCBpbmNsdWRlPUZBTFNFfQ0KbGlicmFyeShrbml0cikNCmxpYnJhcnkoZHBseXIpDQpsaWJyYXJ5KHN0cmluZ3IpDQpsaWJyYXJ5KHRpZHl2ZXJzZSkNCmxpYnJhcnkoaWdyYXBoKQ0KbGlicmFyeShnZ3Bsb3QyKQ0KbGlicmFyeShyZ2wpDQpsaWJyYXJ5KGdncmFwaCkNCmxpYnJhcnkocmVhZHIpDQpsaWJyYXJ5KGRzNHBzeSkNCmxpYnJhcnkobnVtYmVycykNCmxpYnJhcnkocmFuZG9tY29sb1IpIA0Kb3B0aW9ucyhzY2lwZW4gPSA5OTkpDQpvcHRpb25zKHJnbC51c2VOVUxMID0gVFJVRSkgIyBTdXBwcmVzcyB0aGUgc2VwYXJhdGUgd2luZG93Lg0KYGBgDQoNCg0KIyMgUGFydCAxDQpQbGF5aW5nIEplbmdhIHdpdGggdGhlIGVsdmVzDQoNCkZpcnN0LCBjcmVhdGUgdGhlIGJyaWNrcw0KYGBge3J9DQppbnB1dCA8LSByZWFkX2xpbmVzKCJEYXkyMlNhbXBsZS50eHQiKQ0KDQpicmlja3M8LWFzLmRhdGEuZnJhbWUobWF0cml4KG5jb2w9Nixucm93PTApKQ0KZm9yKGkgaW4gMTpsZW5ndGgoaW5wdXQpKXsNCiAgYnJpY2tzPC1yYmluZChicmlja3MsYXMubnVtZXJpYyh1bmxpc3Qoc3RyX3NwbGl0KHN0cl9yZXBsYWNlKGlucHV0W2ldLCJ+IiwiLCIpLCIsIikpKSl9DQpjb2xuYW1lcyhicmlja3MpPC1jKCJ4MSIsInkxIiwiejEiLCJ4MiIsInkyIiwiejIiKQ0KDQojIyMgYWRkIDEgYmVjYXVzZSB3b3JraW5nIHdpdGggUiBpbnN0ZWFkIG9mIGEgbGFuZ3VhZ2UgdGhhdCBzdGFydHMgYXQgMC4NCmJyaWNrczwtYnJpY2tzKzENCmBgYA0KDQpOb3csIHNvcnQgdGhlIGJyaWNrcyBieSB0aGUgbG93ZXN0IFosIHRoZW4gYWRkIGEgbnVtYmVyIHRvIHNob3cgd2hpY2ggYmxvY2sgaXMgZmlyc3QgKCYgc28gb24pDQpgYGB7cn0NCmJyaWNrcyA8LSBicmlja3MgJT4lIHJvd3dpc2UgJT4lIG11dGF0ZShsb3d6PW1pbih6MSx6MikpICU+JSBhcnJhbmdlKGxvd3opICU+JQ0KICByb3dpZF90b19jb2x1bW4odmFyPSJicmlja251bSIpICU+JSBtdXRhdGUoYnJpY2tudW09cGFzdGUwKCJicmljayIsYnJpY2tudW0pKQ0KYnJpY2tzWzE6NSxdDQpgYGANCldpdGggdGhlIGJyaWNrcyBzb3J0ZWQsIGNyZWF0aW5nIGFuIGFydGlmaWNhbCAidG93ZXIiIGZvciB0aGVtIHRvIHNldHRsZSBpbnRvLiAgSXQgd2lsbCBiZSBhIHRocmVlIGRpbWVuc2lvbmFsIGFycmF5IGFuZCB0aGUgbG93ZXN0IGxheWVyIHdpbGwgYmUgImZsb29yIg0KDQpDcmVhdGUgQ29udGFpbmVyIGFuZCBHcmFwaCAobW9zdGx5IGZvciBwYXJ0IDIpDQpgYGB7cn0NCnRvd2VyIDwtIGFycmF5KGNoYXJhY3RlcigpLA0KICAgICAgICAgICAgICAgYyhtYXgoYnJpY2tzJHgxLGJyaWNrcyR4MiksDQogICAgICAgICAgICAgICAgIG1heChicmlja3MkeTEsYnJpY2tzJHkyKSwNCiAgICAgICAgICAgICAgICAgbWF4KGJyaWNrcyR6MSxicmlja3MkejIpKSkNCnRvd2VyWywsMV08LSJmbG9vciINCmBgYA0KDQoNCg0KRnVuY3Rpb24gdG8gc2V0dGxlIHRoZSBibG9ja3MgaW50byB0aGUgdG93ZXIgYW5kIGNyZWF0ZSBhIHN1cHBvcnQgZ3JhcGg6DQpgYGB7cn0NCnNldHRsZTwtZnVuY3Rpb24oYmxpc3QsdHdyKXsNCiAgIyMjIGNyZWF0ZSBhIHN1cHBvcnQgZ3JhcGgNCiAgc3VwcG9ydGdyYXBoPC1tYXRyaXgobmNvbD0yLG5yb3c9MCkNCiAgIyMjIGNyZWF0ZSBhIG5ldyBkYXRhZnJhbWUNCiAgdGlueWI8LWFzLmRhdGEuZnJhbWUobWF0cml4KG5jb2w9OSxucm93PTApKQ0KICAjIyMgZm9yIGVhY2ggcm93IG9mIHRoZSBicmlja2xpc3QNCiAgZm9yKGkgaW4gMTpucm93KGJsaXN0KSl7DQogICAga2VlcGdvaW5nPC1UUlVFDQogICAgY3VycmJyPC1ibGlzdFtpLF0NCiAgICBob3dtYW55bGV2ZWxzPC1kaW0odHdyKVszXQ0KICAgICAgZm9yKHggaW4gY3VycmJyJHgxOmN1cnJiciR4Mil7DQogICAgICAgIGZvcih5IGluIGN1cnJiciR5MTpjdXJyYnIkeTIpew0KICAgICAgICAgIGZvcih6IGluIGN1cnJiciR6MTpjdXJyYnIkejIpew0KICAgICAgICAgICAgaGlnaGVzdGZpbGxlZDwtbWF4KHdoaWNoKCFpcy5uYSh0d3JbeCx5LDE6KGN1cnJiciRsb3d6LTEpXSkpKQ0KICAgICAgICAgICAgaG93bWFueWxldmVsczwtbWluKGhvd21hbnlsZXZlbHMsei1oaWdoZXN0ZmlsbGVkLTEpfX19DQogICAgY3VycmJyJHoxPC1jdXJyYnIkejEtaG93bWFueWxldmVscw0KICAgIGN1cnJiciR6MjwtY3VycmJyJHoyLWhvd21hbnlsZXZlbHMNCiAgICBjdXJyYnIkbG93ejwtY3VycmJyJGxvd3otaG93bWFueWxldmVscw0KICAgICMjIyBvbmNlIGl0IGhhcyBkcm9wcGVkIGFzIGZhciBhcyBwb3NzaWJsZSwgYWRkIHRoZSBicmlja25hbWUgdG8gdGhlIHRvd2VyDQogICAgZm9yKHggaW4gY3VycmJyJHgxOmN1cnJiciR4Mil7DQogICAgICBmb3IoeSBpbiBjdXJyYnIkeTE6Y3VycmJyJHkyKXsNCiAgICAgICAgZm9yKHogaW4gY3VycmJyJHoxOmN1cnJiciR6Mil7DQogICAgICAgICAgdHdyW3gseSx6XTwtY3VycmJyJGJyaWNrbnVtDQogICAgICAgICAgaWYoIWlzLm5hKHR3clt4LHksKHotMSldKSl7c3VwcG9ydGdyYXBoPC1yYmluZChzdXBwb3J0Z3JhcGgsYyh0d3JbeCx5LCh6LTEpXSxjdXJyYnIkYnJpY2tudW0pKX0NCiAgICAgICAgICB9fX0NCiAgICAjIyMgYWRkIHRoZSBuZXcgYnJpY2sgcG9zaXRpb24gdG8gdGhlIG5ldyBicmlja2xpc3QNCiAgICB0aW55YjwtcmJpbmQodGlueWIsY3VycmJyKX0NCiAgIyMjIGNsZWFuIHVwIHRoZSByZXBlYXQgZWRnZXMgaW4gdGhlIHN1cHBvcnQgZ3JhcGggJiBjcmVhdGUgdGhlIHN1cHBvcnQgZ3JhcGgNCiAgc3VwcG9ydGdyYXBoIDwtIHVuaXF1ZShzdXBwb3J0Z3JhcGgpDQogIHN1cHBvcnRncmFwaCA8LXNpbXBsaWZ5KGdyYXBoX2Zyb21fZWRnZWxpc3QoYXMubWF0cml4KHN1cHBvcnRncmFwaCkpKQ0KICBjb2xuYW1lcyh0aW55Yik8LWNvbG5hbWVzKGJsaXN0KQ0KICAjIyMgcmV0dXJuIHRoZSB1cGRhdGVkIHRvd2VyLCB0aGUgbmV3IGJyaWNrbGlzdCBhbmQgdGhlIGxpc3Qgb2YgYWxsIGNvbm5lY3Rpb25zIGJldHdlZW4gYnJpY2tzDQogIGxpc3QodHdyLHRpbnliLHN1cHBvcnRncmFwaCl9DQpgYGANCg0KDQpSdW4gb24gdGhlIGRhdGENCg0KYGBge3J9DQpzZXR0bGluZzwtc2V0dGxlKGJyaWNrcyx0b3dlcikNCnNldHRsZWRicmlja3M8LXNldHRsaW5nW1syXV0NCnNldHRsZWR0b3dlcjwtc2V0dGxpbmdbWzFdXQ0Kc2V0dGxlZGdyYXBoPC1zZXR0bGluZ1tbM11dDQoNCmBgYA0KDQoNCg0KSGVyZSdzIGEgdmlzdWFsIG9mIHRoZSByZWFsIGRhdGEgYm90aCBiZWZvcmUgYW5kIGFmdGVyIHNldHRsaW5nOg0KDQpgYGB7cixpbmNsdWRlPUZBTFNFLGVjaG89RkFMU0V9DQpyZWFsaW5wdXQgPC0gcmVhZF9saW5lcygiLi4vLi4vQWR2ZW50MjAyMy9EYXkyMi50eHQiKQ0KcmVhbGJyaWNrczwtYXMuZGF0YS5mcmFtZShtYXRyaXgobmNvbD02LG5yb3c9MCkpDQpmb3IoaSBpbiAxOmxlbmd0aChyZWFsaW5wdXQpKXsNCiAgcmVhbGJyaWNrczwtcmJpbmQocmVhbGJyaWNrcyxhcy5udW1lcmljKHVubGlzdChzdHJfc3BsaXQoc3RyX3JlcGxhY2UocmVhbGlucHV0W2ldLCJ+IiwiLCIpLCIsIikpKSl9DQpjb2xuYW1lcyhyZWFsYnJpY2tzKTwtYygieDEiLCJ5MSIsInoxIiwieDIiLCJ5MiIsInoyIikNCnJlYWxicmlja3M8LXJlYWxicmlja3MrMQ0KcmVhbGJyaWNrcyA8LSByZWFsYnJpY2tzICU+JSByb3d3aXNlICU+JSBtdXRhdGUobG93ej1taW4oejEsejIpKSAlPiUgYXJyYW5nZShsb3d6KSAlPiUNCiAgcm93aWRfdG9fY29sdW1uKHZhcj0iYnJpY2tudW0iKSAlPiUgbXV0YXRlKGJyaWNrbnVtPXBhc3RlMCgiYnJpY2siLGJyaWNrbnVtKSkNCnJlYWx0b3dlciA8LSBhcnJheShjaGFyYWN0ZXIoKSwNCiAgICAgICAgICAgICAgIGMobWF4KHJlYWxicmlja3MkeDEscmVhbGJyaWNrcyR4MiksDQogICAgICAgICAgICAgICAgIG1heChyZWFsYnJpY2tzJHkxLHJlYWxicmlja3MkeTIpLA0KICAgICAgICAgICAgICAgICBtYXgocmVhbGJyaWNrcyR6MSxyZWFsYnJpY2tzJHoyKSkpDQpyZWFsdG93ZXJbLCwxXTwtImZsb29yIg0KDQpicmlja3BhbGV0dGUgPC0gZGlzdGluY3RDb2xvclBhbGV0dGUobnJvdyhyZWFsYnJpY2tzKSkNCnJlYWxicmlja3M8LWNiaW5kKHJlYWxicmlja3MsYnJpY2twYWxldHRlKQ0KcmVhbHNldHRsZWQ8LXNldHRsZShyZWFsYnJpY2tzLHJlYWx0b3dlcilbWzJdXQ0KYGBgDQoNCg0KYGBge3IsZWNobz1GQUxTRSx3ZWJnbD1UUlVFfQ0KZm9yKGkgaW4gMToobnJvdyhyZWFsc2V0dGxlZCkpKXsNCiAgI3ggZGlmZmVyZW50DQogIGlmKHJlYWxzZXR0bGVkJHgxW2ldIT1yZWFsc2V0dGxlZCR4MltpXSl7DQogICAgZm9yKGogaW4gKHJlYWxzZXR0bGVkJHgxW2ldKToocmVhbHNldHRsZWQkeDJbaV0pKXsNCiAgICAgIHNoYWRlM2QodHJhbnNsYXRlM2QoY3ViZTNkKGNvbCA9IHJlYWxzZXR0bGVkJGJyaWNrcGFsZXR0ZVtpXSksIDIqaisxLCAyKnJlYWxicmlja3MkeTFbaV0rMSwgMipyZWFsYnJpY2tzJHoxW2ldKzEpKQ0KICAgICAgc2hhZGUzZCh0cmFuc2xhdGUzZChjdWJlM2QoY29sID0gcmVhbHNldHRsZWQkYnJpY2twYWxldHRlW2ldKSwgMipqKzI2LCAyKnJlYWxzZXR0bGVkJHkxW2ldKzI2LCAyKnJlYWxzZXR0bGVkJHoxW2ldKzEpKQ0KICAgIH19ZWxzZSBpZihyZWFsc2V0dGxlZCR5MVtpXSE9cmVhbHNldHRsZWQkeTJbaV0pew0KICAgICAgZm9yKGogaW4gKHJlYWxzZXR0bGVkJHkxW2ldKToocmVhbHNldHRsZWQkeTJbaV0pKXsNCiAgICAgICAgc2hhZGUzZCh0cmFuc2xhdGUzZChjdWJlM2QoY29sID0gcmVhbHNldHRsZWQkYnJpY2twYWxldHRlW2ldKSwyKnJlYWxicmlja3MkeDFbaV0rMSwgMipqKzEsIDIqcmVhbGJyaWNrcyR6MVtpXSsxKSkNCiAgICAgICAgc2hhZGUzZCh0cmFuc2xhdGUzZChjdWJlM2QoY29sID0gcmVhbHNldHRsZWQkYnJpY2twYWxldHRlW2ldKSwyKnJlYWxzZXR0bGVkJHgxW2ldKzI2LCAyKmorMjYsIDIqcmVhbHNldHRsZWQkejFbaV0rMSkpfQ0KICAgIH1lbHNle2ZvcihqIGluIChyZWFsc2V0dGxlZCR6MVtpXSk6KHJlYWxzZXR0bGVkJHoyW2ldKSl7DQogICAgICBzaGFkZTNkKHRyYW5zbGF0ZTNkKGN1YmUzZChjb2wgPSByZWFsc2V0dGxlZCRicmlja3BhbGV0dGVbaV0pLDIqcmVhbGJyaWNrcyR4MVtpXSsxLDIqcmVhbGJyaWNrcyR5MVtpXSsxLDIqaisxKSkNCiAgICAgIHNoYWRlM2QodHJhbnNsYXRlM2QoY3ViZTNkKGNvbCA9IHJlYWxzZXR0bGVkJGJyaWNrcGFsZXR0ZVtpXSksMipyZWFsc2V0dGxlZCR4MVtpXSsyNiwyKnJlYWxzZXR0bGVkJHkxW2ldKzI2LDIqaisxKSl9fX0NCg0Kcmdsd2lkZ2V0KCkNCmBgYA0KDQoNClRoZSBzdXBwb3J0IGdyYXBoIHNob3dzIGEgY29ubmVjdGlvbiBiZXR3ZWVuIGV2ZXJ5IGJyaWNrIGFuZCB0aGUgYnJpY2tzIGl0IGlzIHJlc3Rpbmcgb24uICBBIGJyaWNrIGlzIHN0YWJsZSBpZiB0aGVyZSBpcyBhIGNvbm5lY3Rpb24gYmV0d2VlbiBpdCBhbmQgdGhlIGZsb29yLg0KDQpPbmUgd2F5IHRvIHRlc3QgaXMgdG8gcmVtb3ZlIGEgYnJpY2sgYW5kIHRoZW4gc2VlIGlmIGFsbCBvZiB0aGUgb3RoZXIgYnJpY2tzIHN0aWxsIGhhdmUgYSBjb25uZWN0aW9uIHRvIHRoZSBmbG9vci4gIElmIHNvLCB0aGVuIGl0IGNhbiBiZSBzYWZlbHkgZGlzaW50ZWdyYXRlZC4NCklmIG5vdCwgdGhlbiB0aGF0IGJyaWNrIGlzIG5vdCBzYWZlDQoNCmBgYHtyfQ0KcGFydDE8LTANCmZvcihpIGluIDE6bnJvdyhzZXR0bGVkYnJpY2tzKSl7DQogIGNoZWNrZ3JhcGg8LWRlbGV0ZS52ZXJ0aWNlcyhzZXR0bGVkZ3JhcGgsc2V0dGxlZGJyaWNrc1tpLF0kYnJpY2tudW0pDQogIHE8LWRpc3RhbmNlcyhjaGVja2dyYXBoLHY9ImZsb29yIix0bz1WKGNoZWNrZ3JhcGgpLG1vZGU9Yygib3V0IikpWzEsXQ0KICBpZihhbGwocSE9SW5mKSl7cGFydDE8LXBhcnQxKzF9fQ0KDQpwYXJ0MQ0KYGBgDQojIyBQYXJ0IDIgLSANCkZpbmQgdGhlIGNoYWluIHJlYWN0aW9uczoNCg0KYGBge3J9DQpwYXJ0MjwtMA0KDQojIyMgc2FtZSBhcyBiZWZvcmUsIGJ1dCBpbnN0ZWFkIG9mIGNvdW50aW5nIHRoZSBzYWZlIGJyaWNrcywgY291bnQgdGhlIG51bWJlciB0aGF0IHdvdWxkIGZhbGwNCg0KZm9yKGkgaW4gMTpucm93KHNldHRsZWRicmlja3MpKXsNCiAgY2hlY2tncmFwaDwtZGVsZXRlLnZlcnRpY2VzKHNldHRsZWRncmFwaCxzZXR0bGVkYnJpY2tzW2ksXSRicmlja251bSkNCiAgcTwtZGlzdGFuY2VzKGNoZWNrZ3JhcGgsdj0xLHRvPVYoY2hlY2tncmFwaCksbW9kZT1jKCJvdXQiKSlbMSxdDQogIHBhcnQyPC1wYXJ0MiArIGxlbmd0aCh3aGljaChxPT1JbmYpKX0NCg0KcGFydDINCmBgYA0KDQpgYGB7cn0NCmRheTIyYW5zd2VycyA8LWZ1bmN0aW9uKGlucHV0KXsNCiMjIyBzZXQgdXAgYnJpY2tzDQogIGJyaWNrczwtYXMuZGF0YS5mcmFtZShtYXRyaXgobmNvbD02LG5yb3c9MCkpDQpmb3IoaSBpbiAxOmxlbmd0aChpbnB1dCkpew0KICBicmlja3M8LXJiaW5kKGJyaWNrcyxhcy5udW1lcmljKHVubGlzdChzdHJfc3BsaXQoc3RyX3JlcGxhY2UoaW5wdXRbaV0sIn4iLCIsIiksIiwiKSkpKX0NCmNvbG5hbWVzKGJyaWNrcyk8LWMoIngxIiwieTEiLCJ6MSIsIngyIiwieTIiLCJ6MiIpDQoNCiMjIyBhZGQgMSBiZWNhdXNlIHdvcmtpbmcgd2l0aCBSIGluc3RlYWQgb2YgYSBsYW5ndWFnZSB0aGF0IHN0YXJ0cyBhdCAwLg0KYnJpY2tzPC1icmlja3MrMQ0KYnJpY2tzIDwtIGJyaWNrcyAlPiUgcm93d2lzZSAlPiUgbXV0YXRlKGxvd3o9bWluKHoxLHoyKSkgJT4lIGFycmFuZ2UobG93eikgJT4lDQogIHJvd2lkX3RvX2NvbHVtbih2YXI9ImJyaWNrbnVtIikgJT4lIG11dGF0ZShicmlja251bT1wYXN0ZTAoImJyaWNrIixicmlja251bSkpDQojIyMgc2V0IHVwIHRvd2VyDQp0b3dlciA8LSBhcnJheShjaGFyYWN0ZXIoKSwNCiAgICAgICAgICAgICAgIGMobWF4KGJyaWNrcyR4MSxicmlja3MkeDIpLA0KICAgICAgICAgICAgICAgICBtYXgoYnJpY2tzJHkxLGJyaWNrcyR5MiksDQogICAgICAgICAgICAgICAgIG1heChicmlja3MkejEsYnJpY2tzJHoyKSkpDQp0b3dlclssLDFdPC0iZmxvb3IiDQoNCiMjIyBydW4gc2V0dGxpbmcNCnNldHRsaW5nPC1zZXR0bGUoYnJpY2tzLHRvd2VyKQ0Kc2V0dGxlZGJyaWNrczwtc2V0dGxpbmdbWzJdXQ0Kc2V0dGxlZHRvd2VyPC1zZXR0bGluZ1tbMV1dDQpzZXR0bGVkZ3JhcGg8LXNldHRsaW5nW1szXV0gIA0KDQojIyMgcnVuIHBhcnRzIDEgJiAyDQoNCnBhcnQxPC0wDQpwYXJ0MjwtMA0KZm9yKGkgaW4gMTpucm93KHNldHRsZWRicmlja3MpKXsNCiAgY2hlY2tncmFwaDwtZGVsZXRlLnZlcnRpY2VzKHNldHRsZWRncmFwaCxzZXR0bGVkYnJpY2tzW2ksXSRicmlja251bSkNCiAgcTwtZGlzdGFuY2VzKGNoZWNrZ3JhcGgsdj0iZmxvb3IiLHRvPVYoY2hlY2tncmFwaCksbW9kZT1jKCJvdXQiKSlbMSxdDQogIGlmKGFsbChxIT1JbmYpKXtwYXJ0MTwtcGFydDErMX0NCiAgcGFydDI8LXBhcnQyICsgbGVuZ3RoKHdoaWNoKHE9PUluZikpfQ0KICBjKHBhcnQxLHBhcnQyKX0NCg0KYGBgDQoNCmBgYHtyfQ0KZGF5MjIgPC0gZGF5MjJhbnN3ZXJzKGlucHV0KQ0KZGF5MjINCmBgYA==